The present invention relates to a process of deciding class inheritance of an object oriented language and a process and a device for determining a method based on described message passing in execution of a program described in a programming language classified into the object oriented language, and more particularly to a process and a device for determining a method in the object oriented language in which high-speed execution is aimed at by compiling.
In the object oriented language, a data structure called an object holds a procedure called a method. In order to execute the method held by the object, the method is activated by performing message passing to said object from another object. In general, since the object holds a plurality of methods, it is determined by a message selector included in message passing which method is to be activated by the message passing. Since the object holds the methods individually, the activated method differs when the object which is a passing destination of message passing which is called a receiver is different even for the same message selector.
Generally, in the object oriented language, the method is defined by a template of an object called a class, and an object created as an instance of a certain class (an object which belongs to said class) has all the methods declared in said class in common. A hierarchical relationship can be defined between two classes, and the method defined in a class in the super hierarchy is inherited in a class in its sub hierarchy. That is, by defining the hierarchical relationship of classes, it is possible to hold the method defined in a super class in common in a sub class without redefinition.
The above-described hierarchical relationship of classes is such that the direct super class of a certain class is only one, what is called single inheritance. The method is distinguished by a message selector which is defined for every method. This message selector corresponds to a method name. It is not allowed to define a different method having the same message selector in the same class. However, if the class is different, it is possible to define a method having the same message selector. When the method having the same message selector as the method inherited from the super class is defined, the method inherited from the super class is invalidated.
As described above, it is determined by the method held by the receiver and the message selector which method is activated by message passing. In case the object of the receiver is ascertained not at the execution time or in case the object is varied as often as execution, it is required to determine the method at the execution time of message passing. Conventionally, this method determining process has been implemented by retrieving the methods with the message selector obtained from a correspondence table of the class to which the receiver belongs as a key when the method and the message passing are executed in every class as discussed in "Multi-Paradigm Language TAO" written by Takeuchi (Magazine "bit" Vol. 20, No. 7, pp. 67-70, 1988). A dichotomizing search and a hash method are used as the retrieving method in this case.
When the method is inherited in accordance with the hierarchical relationship of classes, a process in which a correspondence table including all the inherited methods is provided in every class and a process in which only the methods defined in the class is provided as the correspondence table are known as the forming process of the correspondence table. In the former case, the method can be determined by retrieving only the correspondence table held by the class to which the receiver belongs as the determining process of the method. In the latter case, when the correspondence table held by the class to which the receiver belongs is retrieved and the corresponding method is found non-existent, it is possible to determine the method by performing similar retrieval operation on the class in the super hierarchy of the relevant class.
In the prior art as the premise of the present invention, it will be explained how to determine the method activated by above-described message passing from the message selector included in the message and the object (receiver) which is the passing destination.
First, the hierarchical relationship among the classes of the present object oriented language and the inheritance of the methods which are the premise of embodiments shown hereafter will be explained with a conventional exemplification with reference to FIG. 1 through FIG. 4.
FIG. 1 shows a hierarchy of classes defined in the present object oriented language and methods defined in respective classes. In FIG. 1, 110 to 114 denote classes and 115 to 118 denote hierarchical relationship among those classes. For example, the hierarchical relationship 115 shows that the direct super class of a class b 111 is a class a 110. 120 to 130 denote the methods defined in respective classes, the alphabetical portions denote method names, and the numerical portions denote explanatory symbols affixed for the purpose of distinguishing different methods. That is, the method A1 (120), the method A2 (123) and the method A3 (125) are different methods having the same method name A. The class b 111 inhibits the method Al (120), the method B1 (121) and the method C1 (122) from the class a 110 which is the super class thereof. However, since the method A2 (123) and the method D1 (124) are defined in the class b 111, inheritance of the method A1 (120) is invalidated, and the methods held in the class b 111 are the method A2 (123), the method B1 (121), the method C1 (122) and the method D1 (124).
Next, in FIG. 2, an object showing a polygon will be explained as a more concrete illustration of the classes of the object as compared with FIG. 1. As shown in this FIG. 2, a triangle, a quadrangle and a pentagon are defined as sub classes of the polygon. Furthermore, an isosceles triangle is defined as a sub class of the triangle and an equilateral triangle is defined as the sub class of this isosceles triangle. It is possible to define a parallelogram as the sub class of the quadrangle and a rectangle and a rhombus as the sub classes of this parallelogram. Such a relationship illustrates the hierarchy of the polygon.
It is possible to define a method in each of these classes. For example, as shown in FIG. 3, a method AREA which seeks after an area can define the methods. Here, a method which is applicable to all the polygons is defined in the class polygon. This method is referred to as AREA 1 (the title if AREA, but 1 is affixed for the sake of distinction). Further, since the area of a triangle is obtained as "base.times.height/2", AREA 2 which executes "base.times.height/2" can be defined for the triangle. Similarly, AREA 4 which executes "one side.times..sqroot.3/2" can be defined for the equilateral triangle, and AREA 5 which executes "longer side.times. shorter side" can be defined for the square. In such a manner, it is possible to define classes and methods as shown in FIG. 3.
The hierarchical relationship of the classes and the inheritance of the methods shown in FIG. 1 are consolidated in FIG. 4.
In the next place, the relationship between the message passing and the methods activated by said message passing will be explained with exemplifications shown in FIG. 1 through FIG. 4. The message passing from a certain object to another object in the present object oriented language is described as shown hereunder for instance. EQU (send ?X A(3))
In this exemplification, ?X denotes a variable indicating an object which is a receiver of the message sending, A denotes a message selector and 3 denotes a parameter. By means of this message passing, those methods that accord with the message selector A are activated among those methods held by the classes to which ?X belongs. Here, when ?X is an object which belongs to the class c 112, the activated method is the method A3 (125), and when ?X is an object which belongs to the class b 111 or the class d 113, the activated method is the method A2 (123), and further, when ?X is an object which belongs to the class a 110 or the class e 114, the activated method is the method A1 (120). The foregoing is determined univocally from a column 143 as defined and inherited methods in FIG. 4.
Similarly, in case of message passing: EQU (send ?X D(3))
p When ?X is an object which belongs to the class b 111, the class c 112 or the class d 113, the activated method is the method D1 (124). When ?X is an object which belongs to the class e 114, the activated method is the method D2 (130), and when ?X is an object which belongs to the class a 110, the activated method does not exist, and an execution time error is produced.
Two types of conventional processes of the process of determining a method which is activated by message passing will be explained hereafter.
First of all, a conventional process I includes a data structure which holds a summary with respect to every class of the direct super class of said class and the methods defined in those classes. This corresponds to a class column 140, a super class column 141 and a defined method column 142 shown in FIG. 4. The processing of determining a method using above-described data structure is shown in FIG. 5.
In this processing, a class to which an object corresponding to the receiver belongs is obtained first (step 150). Here, every object belongs to some class, and it can be found easily which object belongs to which class because of under control of a processing system. However, the procedure has no direct relationship with the present invention. Hence its explanation is omitted. The processing for obtaining a class of an object is discussed in detail in "Small talk 80 The Language and it's Implementation", 1983 by Adele Goldberg and David Robson published by Addison-Wesley Publishing Company.
After the processing in this step 150, it is searched to find whether a method which accords with the message selector exists in the method defined in that class or not (step 151). When it exists, that method is determined to be the method to be activated (step 155). When it does not exist, it is checked whether a super class of that class exists or not (step 152). If a direct super class does not exist, any method to be activated does not exist, producing execution time error (step 154). If a direct super class exists, the searched class is determined as the direct super class thereof (step 153), and the step 151 and thereafter are repeated.
Next, in a conventional process II, there is provided in every class a data structure which holds a summary of methods defined in that class and methods inherited from super classes. The foregoing corresponds to the class column 140 and the column 143 of defined and inherited methods shown in FIG. 4. The processing of determining a method using this data structure is shown in FIG. 6.
In the present processing, a class to which an object corresponding to the receiver is obtained first in a similar manner as the conventional process I (step 160), and it is searched whether any method which accords with the message selector exists in the methods defined and inherited in that class or not (step 161). When it exists, that method is determined to be the method to be activated (step 162). Further, when it does not exist, a method to be activated does not exist, producing an execution time error (step 163).
In the conventional process II, the capacity of the data structure of the method summary for every class is larger as compared with the conventional process I. However, since the method can be determined by means of searching of one data structure only, this process is capable of determining a method at a higher speed than the conventional process I. Besides, dichotonizing search using a binary search table, a hash method using a hash table and the like are used for the data structure of method summary and the searching method thereof.
In above-described both conventional processes I and II, search processing of the method is performed whenever message passing is executed Accordingly, when the summary of the method which becomes a searching object is increased, searching takes time, thus reducing the execution speed as described previously.
As described with reference to above illustrations, there is such a problem in a conventional technique that, when an object of a receiver is not ascertained to be the execution time, or then it is varied as often as every execution, it is required to retrieve the correspondence table of the methods and the message selectors whenever message passing is executed, thus taking a long time for processing. In particular, when the types of methods held by the same object are increased, the speed is lowered to a great extent. Accordingly, the execution speed of an interpreter of the object oriented language in which above-described method determining process is adopted is low, and the execution speed of an objective code which is output by a compiler which outputs above-described method determining process as an objective code is also low.
Further, there is such a problem that, when a method is determined without retrieving the correspondence table of the methods and the message selectors in every message passing, it is required to judge the relationship of inheritance between the class to which the receiver which is the passing destination of message passing belongs and the class defining the method at the execution time, and the speed at the execution time is lowered if the speed of judging this relationship of inheritance is low.